//class Solution {
//    public boolean backspaceCompare(String s, String t) {
//        //法一 栈
//        StringBuilder a = new StringBuilder(s.length());
//        StringBuilder b = new StringBuilder(t.length());
//
//        for (int i = 0; i < s.length(); i++) {
//            if(s.charAt(i) != 35) a.append(Character.toString(s.charAt(i)));
//            else {
//                if(a.length() != 0) a.deleteCharAt(a.length() - 1);
//            }
//        }
//
//        for (int i = 0; i < t.length(); i++) {
//            if(t.charAt(i) != 35) b.append(Character.toString(t.charAt(i)));
//            else {
//                if(b.length() != 0) b.deleteCharAt(b.length() - 1);
//            }
//        }
//
//        return a.toString().equals(b.toString());
//
//
//        //法二 进阶？？？ 双指针
//
//
//
//
//    }
//}

//二刷-------------------!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

class Solution {
    public boolean backspaceCompare(String s, String t) {
        /**
         * s、t从后向前遍历，比较每一个元素，相等则继续，不等则false
         *  当遇到一个'#'，跳过一个元素（）
         *
         */
        int sNum = 0, tNum = 0; //分别记录s t 中#的数量
        int i = s.length()-1, j = t.length()-1; //指向最后一个元素
        while (true){
            while (i >= 0){ //从后向前，消除s的#
                if (s.charAt(i) == '#') sNum++;
                else {
                    if (sNum > 0) sNum--;
                    else break;
                }
                i--;
            }
            while (j >= 0) { //从后向前，消除t的#
                if (t.charAt(j) == '#') tNum++;
                else {
                    if (tNum > 0) tNum--;
                    else break;
                }
                j--;
            }
            //后半部分#消除完了，接下来比较s[i] != t[j]
            if (i < 0 || j < 0) break;  // s或t遍历到头了
            if (s.charAt(i) != t.charAt(j)) return false;
            i--;j--;
        }

        //说明s、t同时遍历完成
        if (i == -1 && j == -1) return true;
        return false;
    }
}